package util;

import bean.ConflictWorker;
import bean.Task;
import bean.TaskTeam;
import bean.Worker;
import org.gavaghan.geodesy.Ellipsoid;
import org.gavaghan.geodesy.GlobalCoordinates;

import java.util.ArrayList;
import java.util.HashSet;

import static util.GreedyUtil.getDistanceMeter;

public class DivideConquerUtil {

    GreedyUtil gUtil = new GreedyUtil();

    /**
     * g-D&C方法
     * @param workers
     * @param tasks
     */

    public ArrayList<TaskTeam> dc(ArrayList<Worker> workers, ArrayList<Task> tasks) {
        //放入当前轮次解决冲突后的TaskTeam
        ArrayList<TaskTeam> Ip = new ArrayList<>();
        int g = 5;
        ArrayList<ArrayList<Task>> Ps = decomposition(tasks, g);
        for (ArrayList<Task> Psi : Ps) {
            if (Psi.size() > 1) {
                dc(workers,Psi);
            }
            TaskTeam Ips = greedyMatch(workers, Psi.get(0));
            if (Ips != null) {
                Ip.add(Ips);
            }
        }

        //TODO 要有递归的终止条件

        for (int i = 0; i < Ip.size(); i++) {

           /* 别整第一个和第二个比较的事。。。
            //如果i == 0，则第一个和第二个解决冲突
            if (i == 0) {
                //先判断是否冲突
                TaskAssignUtil tUtil = new TaskAssignUtil();
                boolean conflict = tUtil.isConflict(Ip.get(0).getWorkers(), Ip.get(1).getWorkers());
                //如果有冲突则解决冲突
                if (conflict) {
                    Ip = twoTeamReconcile(Ip, workers);
                }
                //如果没有冲突，则不要改动Ip
                i++;
            }
            //如果是第三个和前面两个比较
            */

            if (i == 0) {

            }

        }

        //TODO  1111 还可以再加一个Ip的class，包含ArrayList<TaskTeam> 和 指针（指向最后一个解决完冲突的TaskTeam），
        // 又感觉第45行不能赋值，而是要add！！！！雀食！！！！

        //TODO 111 注意，递归的时候就维护这一个Ip
        // 冲突解决完不能完成的任务就从TaskTeam中删除，
        // 这样的递归应该就没问题吧！
        return Ip;
    }


    /**
     * 为冲突的工人conflictWorkers选择最佳的任务，并确认
     * @param conflictWorkers
     * @param taskTeams
     * @param taskTeamsY
     * @param taskTeamsN
     * @param Wp
     */
    public void selectBetterTaskForWorker(ArrayList<ConflictWorker> conflictWorkers, ArrayList<TaskTeam> taskTeams, ArrayList<TaskTeam> taskTeamsY, ArrayList<TaskTeam> taskTeamsN, ArrayList<Worker> Wp) {

        for (ConflictWorker cw : conflictWorkers) {
            TaskTeam bestTaskTeam = new TaskTeam();
            double bestValue = 99999999999999.0;

            for (TaskTeam tt : cw.getTaskTeams()) {
                //先把当前工人从TaskTeam的team中删除
                tt.getTeam().remove(cw.getConflictWorker());
                //找出当前工人的最佳任务
                double nowValue = gUtil.distance(tt.getTask(), cw.getConflictWorker()) / gUtil.maxItem2(tt.getTeam(), cw.getConflictWorker(), tt.getTask().getSkills());
                if (nowValue < bestValue) {
                    bestValue = nowValue;
                    bestTaskTeam = tt;
                }
            }
            //确认此最佳任务
            bestTaskTeam.getTeam().add(cw.getConflictWorker());
            taskTeamsY.add(bestTaskTeam);
            taskTeams.remove(bestTaskTeam);
            for (Worker bw : bestTaskTeam.getTeam()) {
                Wp.remove(bw);
            }

        }
    }


    /**
     * 确认不冲突的工人和任务
     * @param Wp
     * @param conflictWorkers
     * @param taskTeams
     * @return
     */
    public ArrayList<TaskTeam> confirmWorker(ArrayList<Worker> Wp, ArrayList<ConflictWorker> conflictWorkers, ArrayList<TaskTeam> taskTeams) {
        ArrayList<TaskTeam> taskTeamsY = new ArrayList<>();
        ArrayList<TaskTeam> conflictTaskTeams = new ArrayList<>();
        for (ConflictWorker cw : conflictWorkers) {
            for (TaskTeam tt : cw.getTaskTeams()) {
                conflictTaskTeams.add(tt);
            }
        }

        ArrayList<TaskTeam> notConflictTaskTeams = new ArrayList<>();

        for (TaskTeam tt : taskTeams) {
            boolean conflict = false; //false此任务不冲突的
            for (TaskTeam tt2 : conflictTaskTeams) {
                if (tt.equals(tt2)) {
                    conflict = true;
                }
            }
            if (!conflict) {
                notConflictTaskTeams.add(tt);
            }
        }

        for (TaskTeam tt : taskTeams) {
            for (TaskTeam tt2 : notConflictTaskTeams) {
                if (tt.equals(tt2)) {
                    taskTeamsY.add(tt);
                }
            }
        }

        for (TaskTeam tt : taskTeamsY) {
            for (Worker w : tt.getTeam()) {
                Wp.remove(w);
            }
        }

        for (TaskTeam tty : taskTeamsY) {
            taskTeams.remove(tty);
        }

        return taskTeamsY;
    }

    /**
     * 找到有冲突的工人
     * @param taskTeams
     * @return
     */
    public ArrayList<ConflictWorker> findConflictWorkers(ArrayList<TaskTeam> taskTeams) {

        ArrayList<ConflictWorker> conflictWorkers = new ArrayList<>();

        for (TaskTeam tt1 : taskTeams) {
            for (Worker w1 : tt1.getTeam()) {

                ArrayList<TaskTeam> conflictTaskTeams = new ArrayList<>();

                for (TaskTeam tt2 : taskTeams) {
                    if (tt1.equals(tt2)) {
                        continue;
                    }
                    for (Worker w2 : tt2.getTeam()) {
                        if (w1.getId() == w2.getId()) {
                            conflictTaskTeams.add(tt2);
                        }
                    }
                }

                if (conflictTaskTeams.size() != 0) {
                    conflictTaskTeams.add(tt1);
                    ConflictWorker cWorker = new ConflictWorker();
                    cWorker.setConflictWorker(w1);
                    cWorker.setTaskTeams(conflictTaskTeams);
                    conflictWorkers.add(cWorker);
                }

            }
        }

        ArrayList<ConflictWorker> reWorkers = new ArrayList<>();

        for (int i = 0; i < conflictWorkers.size(); i++) {
            ConflictWorker cw1 = conflictWorkers.get(i);

            for (int j = i + 1; j < conflictWorkers.size(); j++) {
                ConflictWorker cw2 = conflictWorkers.get(j);
                if (cw1.getConflictWorker().equals(cw2.getConflictWorker())) {
                    reWorkers.add(cw2);
                }
            }
        }

        for (ConflictWorker cw : reWorkers) {
            conflictWorkers.remove(cw);
        }

        return conflictWorkers;
    }

    /**
     * 为一个任务组成团队，
     * Attention！此团队不一定可以满足任务的技能要求，有效工人全部遍历完就结束组队
     * @param tjWorkers 任务tj的有效工人
     * @param tj 当前任务
     * @return taskTeam：任务及对应的团队
     */
    public TaskTeam formTeam(ArrayList<Worker> tjWorkers, Task tj) {
        TaskTeam taskTeam = new TaskTeam();

        //先形成团队，能招几个人算几个人，当工人们tjWorkers全部遍历完，或者工人能够完成任务时break
        // 最后在外部判断此团队是否可以满足任务要求
        //在argMax保证了熵值不为0
        ArrayList<Worker> tjTeam = new ArrayList<>();
        for (Worker tjW : tjWorkers) {
            if (gUtil.isSkillsSatisfy(tj.getSkills(),tjTeam)) {
                break;
            }
            Worker maxWorker = argMax(tjWorkers,tj,tjTeam);
            if (maxWorker.getId() != 0.0) {
                tjTeam.add(maxWorker);
            }
        }

        //此出判断团队是否可以完成任务
        boolean satisfy = gUtil.isSkillsSatisfy(tj.getSkills(), tjTeam);
        if (satisfy) {
            taskTeam.setTask(tj);
            taskTeam.setTeam(tjTeam);
            taskTeam.setValidWorkers(tjWorkers);
            taskTeam.setCompleted(true);
        }else {
            taskTeam.setTask(tj);
            taskTeam.setTeam(tjTeam);
            taskTeam.setValidWorkers(tjWorkers);
            taskTeam.setCompleted(false);
        }

        return taskTeam;
    }


    /**
     * 为当前任务tj找出性价比最高的工人
     * 保证了团队熵值不为0
     * @param tjWorkers 任务tj的有效工人
     * @param tj 任务tj
     * @param tjTeam 任务tj的团队
     * @return 性价比最高的工人
     */
    public Worker argMax(ArrayList<Worker> tjWorkers, Task tj, ArrayList<Worker> tjTeam) {
        double argMax = 0;
        Worker maxWorker = new Worker();
        for (Worker worker : tjWorkers) {
            //在这里保证了熵值不为0
            if (tjTeam.size() != 0) {
                if (tjTeam.get(0).getCluster() == worker.getCluster()) {
                    continue;
                }
            }
            int maxItem1 = gUtil.maxItem1(tjTeam,tj.getSkills());
            int maxItem2 = gUtil.maxItem2(tjTeam,worker,tj.getSkills());
            double value = (maxItem2 - maxItem1) / gUtil.distance(tj,worker);
            if ( value>argMax ) {
                argMax = value;
                maxWorker = worker;
            }
        }
        return maxWorker;
    }

    /**
     * 把m个任务分成g组
     * @param Tp 任务集合
     * @param g
     * @return 二维数组Task
     */
    public ArrayList<ArrayList<Task>> decomposition (ArrayList<Task> Tp, int g) {
        ArrayList<ArrayList<Task>> Ps = new ArrayList<>();
        int size = Tp.size();

        for (int i = 0; i < g; i++) {
            ArrayList<Task> Pi = new ArrayList<>();
            Task task = Tp.remove(0);
            Pi.add(task);

            //找到task周围最近的size/g - 1个任务
            //如果i == g - 1， 则把剩下的任务都装在一起
            if (i == g - 1) {
                for (Task t : Tp) {
                    Pi.add(t);
                }
                Tp.clear();
                Ps.add(Pi);
                return Ps;
            }
            for (int j = 0; j < size / g - 1; j++) {
                Task nearest = findNearest(task, Tp);
                Pi.add(nearest);
                Tp.remove(nearest);
            }
            Ps.add(Pi);
        }
        return Ps;
    }

    /**
     * 找到距离任务t最近的一个任务
     * @param t 任务t
     * @param ts 任务集合ts
     * @return 距离任务t最近的任务
     */
    public Task findNearest(Task t, ArrayList<Task> ts) {
        if (ts == null) {
            return null;
        }

        Task nearestTask = ts.get(0);
        double nearestDistance = distance(t,nearestTask);
        for (Task ti: ts) {
            double distance = distance(t, ti);
            if (distance < nearestDistance) {
                nearestTask = ti;
                nearestDistance = distance;
            }
        }

        return nearestTask;
    }

    /**
     * 计算工人和任务之间的距离（m）
     * @param t1 任务1
     * @param t2 任务2
     * @return 距离（m）
     */
    public double distance(Task t1, Task t2) {
        return calculateTheDistance(t1.getLongitude(),t1.getLatitude(),t2.getLongitude(), t2.getLatitude());
    }

    /**
     * 计算两个经纬度点的距离（m）
     * @param longitudeFrom 起点经度
     * @param latitudeFrom  起点纬度
     * @param longitudeTo   终点经度
     * @param latitudeTo   终点纬度
     * @return
     */
    public static long calculateTheDistance(double longitudeFrom, double latitudeFrom, double longitudeTo, double latitudeTo) {
        GlobalCoordinates source = new GlobalCoordinates(latitudeFrom, longitudeFrom);
        GlobalCoordinates target = new GlobalCoordinates(latitudeTo, longitudeTo);
        Long distanceMeter = Math.round(getDistanceMeter(target, source, Ellipsoid.Sphere));
        return distanceMeter;
    }


    /**
     * 两个任务去冲突
     * @param Ip
     * @param workers
     * @return
     */
    public ArrayList<TaskTeam> twoTeamReconcile(ArrayList<TaskTeam> Ip, ArrayList<Worker> workers) {
        GreedyUtil gUtil = new GreedyUtil();

        Task t1 = Ip.get(0).getTask();
        Task t2 = Ip.get(1).getTask();

        ArrayList<Worker> workers1 = Ip.get(0).getTeam();
        ArrayList<Worker> workers2 = Ip.get(1).getTeam();

        //先找到有冲突的工人
        ArrayList<Worker> workersConflict = new ArrayList<>();
        for (Worker w1 : workers1) {
            for (Worker w2 : workers2) {
                if (w1.equals(w2)) {
                    workersConflict.add(w1);
                    continue;
                }
            }
        }
        //判断工人对哪个队的性价比高，分配给哪个队
        //性价比 = 成本 / 所需要的技能数
        for (Worker w : workersConflict) {
            //删除性价比较差的TaskTeam中的worker
            TaskTeam worseTaskTeam = getWorseTaskTeamForWorker(w, Ip);
            worseTaskTeam.getTeam().remove(w);
            worseTaskTeam.setCompleted(false);
            //TODO 1
            //为此TaskTeam匹配新的工人

            //TODO 2
            //如果匹配不到新的工人则删除此TaskTeam



        }



        ArrayList<TaskTeam> taskTeams = new ArrayList<>();



        //TODO
        //注意！！！此处的taskTeams确定是不是最终的，可能要修改。
        return taskTeams;
    }


    /**
     * 找到较差的分配实例 For worker
     * value = 成本 / 工人被任务所需要的技能数（value越大，则越差）
     *  找到较坏的分配实例，然后从此分配实例TaskTeam中删除此工人，还要把isCompleted置为false
     * @param w
     * @param Ip
     * @return TaskTeam,是一个具体的分配实例（方便把实例中的工人删除）
     */
    public TaskTeam getWorseTaskTeamForWorker(Worker w, ArrayList<TaskTeam> Ip) {
        GreedyUtil gUtil = new GreedyUtil();

        Task t1 = Ip.get(0).getTask();
        Task t2 = Ip.get(1).getTask();

        //对于任务1
        //计算成本
        double cost1 = gUtil.distance(t1, w) / 100.0;
        //找到技能数
        int skillsNum1 = getSkillsNum(w, t1);
        //得到性价比
        double value1 = cost1 / skillsNum1;

        //对于任务2
        //计算成本
        double cost2 = gUtil.distance(t2, w) / 100.0;
        //找到技能数
        int skillsNum2 = getSkillsNum(w, t2);
        //得到性价比
        double value2 = cost2 / skillsNum2;

        if (value1 < value2) {
            return Ip.get(1);
        }else {
            return Ip.get(0);
        }
    }


    /**
     * 得到工人和任务的 技能重合数
     * 由于此工人、任务是在TaskTeam中，所以最少有一个技能重合
     * @param w
     * @param task
     * @return
     */
    public int getSkillsNum(Worker w, Task task) {
        HashSet<Double> intersection = new HashSet<>();
        //比较当前工人的技能和任务所需技能，如果工人技能是任务所需的，则将此技能加入交集intersection
        for (Double wSkill : w.getSkills()) {
            for (Double tSkill : task.getSkills()) {
                if (wSkill.doubleValue() == tSkill.doubleValue()) {
                    intersection.add(wSkill.doubleValue());
                }
            }
        }
        return intersection.size();
    }

    /**
     * 为任务匹配团队
     * 《TaskAssignment》的算法MS-SC gD&C 第8行
     * @param workers
     * @param task
     * @return TaskTeam 或 null （注意判断null情况）
     */
    public TaskTeam greedyMatch(ArrayList<Worker> workers, Task task) {
        GreedyUtil gUtil = new GreedyUtil();

        // 为每个任务tj找到有效工人validWorkers
        ArrayList<Worker> validWorkers = gUtil.getTjWorkers(task, workers);
        // 为每个任务task形成团队
        ArrayList<Worker> taskTeam = gUtil.formTeam(validWorkers, task);
        //判断团队是否可以完成任务
        boolean satisfy = gUtil.isSkillsSatisfy(task.getSkills(), taskTeam);
        if (satisfy) {
            TaskTeam taskTeam1 = new TaskTeam(task, taskTeam,true);
            return taskTeam1;
        }else {
            return null;
        }
    }



}
